import copy
import random

class Card:
    def __init__(self, suit, value=None):
        assert suit in ['條', '餠', '萬', '中', '發', '空', '花']
        self.suit = suit
        if suit in ['條', '餠', '萬']:
            assert value in range(1, 10)
            self.value = value
        else:
            self.value = None

    def __str__(self):
        if self.suit in ['條', '餠', '萬']:
            chDict = ['一', '二', '三', '四', '五', '六', '七', '八', '九']
            return f'{chDict[self.value-1]}{self.suit}'
        else:
            return f' {self.suit} '
        
    def __eq__(self, other) -> bool:
        if isinstance(other, Card):
            if self.suit != other.suit: return False
            if self.value != other.value: return False
            return True
        return False

    def __hash__(self) -> int:
        return hash((self.suit, self.value))

    def __repr__(self) -> str:
        return str(self)

def new_deck():
    cards = []
    for suit in ['條', '餠', '萬']:
        for value in range(1, 10):
            cards.append(Card(suit, value))
    for suit in ['中', '發', '空']:
        for value in range(4):
            cards.append(Card(suit))
    cards.append(Card('花'))
    return cards

class Game:
    def __init__(self):
        # self.top_left = [[],[],[]]
        self.stack = [] # top_left
        self.main_columns = [[] for i in range(8)]
        self.flower_grid = []
        self.stick_collect_progress = 0
        self.circle_collect_progress = 0
        self.wan_collect_progress = 0
        self.all_zhong_collected = False
        self.all_fa_collected = False
        self.all_blank_collected = False
        deck = new_deck()
        random.shuffle(deck)
        for i, card in enumerate(deck):
            self.main_columns[i%8].append(card)

    def __deepcopy__(self, memo):
        game = Game()
        # game.top_left = copy.deepcopy(self.top_left)
        game.stack = copy.deepcopy(self.stack)
        game.stick_collect_progress = self.stick_collect_progress
        game.circle_collect_progress = self.circle_collect_progress
        game.wan_collect_progress = self.wan_collect_progress
        game.main_columns = copy.deepcopy(self.main_columns)
        game.flower_grid = copy.deepcopy(self.flower_grid)
        game.all_zhong_collected = self.all_zhong_collected
        game.all_fa_collected = self.all_fa_collected
        game.all_blank_collected = self.all_blank_collected
        return game

    @property
    def flower_collected(self):
        return len(self.flower_grid)==1

    def __eq__(self, other) -> bool:
        assert isinstance(other, Game)
        if self.flower_collected != other.flower_collected: return False
        if self.all_zhong_collected != other.all_zhong_collected: return False
        if self.all_fa_collected != other.all_fa_collected: return False
        if self.all_blank_collected != other.all_blank_collected: return False
        # if set([item[0] for item in self.top_left if len(item)>0])-{None} != set([item[0] for item in other.top_left if len(item)>0])-{None}: return False
        if set(self.stack)!= set(other.stack): return False
        if self.stick_collect_progress != other.stick_collect_progress: return False
        if self.circle_collect_progress != other.circle_collect_progress: return False
        if self.wan_collect_progress != other.wan_collect_progress: return False
        for c in range(8):
            if len(self.main_columns[c]) != len(other.main_columns[c]): return False
            for i in range(len(self.main_columns[c])):
                if self.main_columns[c][i] != other.main_columns[c][i]: return False
        return True

    def success(self) -> bool:
        if not self.flower_collected: return False
        if not self.all_zhong_collected: return False
        if not self.all_fa_collected: return False
        if not self.all_blank_collected: return False
        if not all(len(column)==0 for column in self.main_columns): return False
        # if not all(len(grid)==0 for grid in self.top_left): return False
        if not len(self.stack)==0: return False
        # if not all(len(grid)==9 for grid in self.top_right): return False
        if not self.stick_collect_progress==9: return False
        if not self.circle_collect_progress==9: return False
        if not self.wan_collect_progress==9: return False
        return True

    def move(self, source, target):
        area_s, index_s = source
        area_t, index_t = target
        card = None
        if area_s=='top_left': # fixme
            card = self.top_left[index_s].pop()
        elif area_s=='main':
            card = self.main_columns[index_s].pop()
        else:
            raise ValueError('Invalid source area')

        if area_t=='top_left':
            self.top_left[index_t].append(card)
        elif area_t=='main':
            self.main_columns[index_t].append(card)
        elif area_t=='top_right':
            # self.top_right[index_t].append(card)
            if card.suit == '條':
                self.stick_collect_progress += 1
            elif card.suit == '餠':
                self.circle_collect_progress += 1
            elif card.suit == '萬':
                self.wan_collect_progress += 1
            else:
                raise ValueError(f'Card from {source} is not a number')
        elif area_t=='flower_grid':
            self.flower_grid.append(card)
        else:
            raise ValueError('Invalid target area')

    def collect_all_of_suit(self, suit):
        assert suit in ['中', '發', '空']
        card_positions = []
        top_left_available_index = None
        top_left_occupied_index = None
        for i in range(3):
            if len(self.top_left[i])>0 and self.top_left[i][0] is not None and self.top_left[i][0].suit==suit:
                card_positions.append(('top_left', i))
                if top_left_occupied_index==None:
                    top_left_occupied_index = i
            if len(self.top_left[i])==0 and top_left_available_index==None:
                top_left_available_index = i
        for i in range(8):
            if len(self.main_columns[i])>0 and self.main_columns[i][-1].suit==suit:
                card_positions.append(('main', i))
        assert len(card_positions)==4
        assert top_left_available_index or top_left_occupied_index
        index_t = top_left_available_index if top_left_available_index is not None else top_left_occupied_index
        for i in range(4):
            area_s, index_s = card_positions[i]
            if area_s=='top_left':
                self.top_left[index_s].pop()
            elif area_s=='main':
                self.main_columns[index_s].pop()
        self.top_left[index_t].append(None)
        if suit=='中': self.all_zhong_collected = True
        elif suit=='發': self.all_fa_collected = True
        elif suit=='空': self.all_blank_collected = True

    def smart_move(self, source, target):
        '''
        move with safety check
        '''
        if len(target)==1: target = list(target)+[None]
        area_s, index_s = source
        area_t, index_t = target
        card = None
        if area_s=='top_left':
            if area_t=='top_left':
                raise ValueError('Cannot move from top_left to top_left')
            if index_s<0 or index_s>2:
                raise ValueError('Invalid index')
            if len(self.top_left[index_s])==0:
                raise ValueError('No card in this place')
            if len(self.top_left[index_s])!=1:
                raise ValueError('More than one card in this place')
            card = self.top_left[index_s].pop()
        elif area_s=='main':
            if area_t=='main' and index_s==index_t:
                raise ValueError('Cannot move to the same column')
            if index_s<0 or index_s>7:
                raise ValueError('Invalid index')
            if len(self.main_columns[index_s])==0:
                raise ValueError('No card in this place')
            card = self.main_columns[index_s].pop()
        else:
            raise ValueError('Invalid source area')

        if area_t=='top_left':
            if index_t==None:
                for i in range(3):
                    if len(self.top_left[i])==0:
                        index_t = i
                        break
                if index_t==None:
                    raise ValueError('No empty place in top_left')
            if index_t<0 or index_t>2:
                raise ValueError('Invalid index')
            if len(self.top_left[index_t])>0:
                raise ValueError('Card already in this place')
            self.top_left[index_t].append(card)
        elif area_t=='main':
            if index_t<0 or index_t>7:
                raise ValueError('Invalid index')
            column = self.main_columns[index_t]
            if len(column)>0 and column[-1].suit not in {'條', '餠', '萬'}-card.suit:
                raise ValueError(f'Cannot put card from {source} to {target}')
            column.append(card)
        elif area_t=='top_right':
            if card.suit == '條':
                if card.value==self.stick_collect_progress+1:
                    self.stick_collect_progress += 1
                else:
                    raise ValueError(f'Cannot collect {card}')
            elif card.suit == '餠':
                if card.value==self.circle_collect_progress+1:
                    self.circle_collect_progress += 1
                else:
                    raise ValueError(f'Cannot collect {card}')
            elif card.suit == '萬':
                if card.value==self.wan_collect_progress+1:
                    self.wan_collect_progress += 1
                else:
                    raise ValueError(f'Cannot collect {card}')
            else:
                raise ValueError(f'Card from {source} is not a number')
        elif area_t=='flower_grid':
            if len(self.flower_grid)>0:
                raise ValueError('Flower already collected')
            if card.suit != '花':
                raise ValueError(f'Card from {source} is not a flower')
            self.flower_grid.append(card)
        else:
            raise ValueError('Invalid target area')

    def __str__(self):
        result = ''
        for grid in self.top_left:
            if len(grid)>0:
                content = grid[0]
                if content==None: content = 'XXXX'
            else: content = '    '
            result += f'[{content}]'
        result += '中' if self.all_zhong_collected else '  '
        result += '發' if self.all_fa_collected else '  '
        result += '空' if self.all_blank_collected else '  '
        result += f'({self.flower_grid[0] if len(self.flower_grid)>0 else "    "})'
        result += f'[{Card("條", self.stick_collect_progress) if self.stick_collect_progress>0 else "    "}]'
        result += f'[{Card("餠", self.circle_collect_progress) if self.circle_collect_progress>0 else "    "}]'
        result += f'[{Card("萬", self.wan_collect_progress) if self.wan_collect_progress>0 else "    "}]'
        result += '\n'
        for j in range(max([len(column) for column in self.main_columns])):
            for i in range(8):
                if j < len(self.main_columns[i]):
                    result += f'[{self.main_columns[i][j]}]'
                else:
                    result += f'      '
            result += '\n'
        return result

    def all_possible_moves(self):
        result = []
        # 1. normal move
        # 1.1 all possible source
        all_possible_source = []
        # 1.1.1 source from top_left
        for i in range(3):
            if len(self.top_left[i])>0 and self.top_left[i][0] is not None:
                card = self.top_left[i][0]
                all_possible_source.append(('top_left', i, card))
        # 1.1.2 source from main
        for i in range(8):
            if len(self.main_columns[i])>0:
                card = self.main_columns[i][-1]
                all_possible_source.append(('main', i, card))
        # 1.2 all possible target
        all_possible_target = []
        # 1.2.1 target to top_left
        for i in range(3):
            if len(self.top_left[i])==0:
                all_possible_target.append(('top_left', i, None))
        # 1.2.2 target to main
        for i in range(8):
            if len(self.main_columns[i])==0:
                all_possible_target.append(('main', i, None))
            elif self.main_columns[i][-1].suit in {'條', '餠', '萬'}:
                card = self.main_columns[i][-1]
                all_possible_target.append(('main', i, card))
        # 1.2.3 target to top_right
        # for i in range(3):
        #     if len(self.top_right[i])==0:
        #         all_possible_target.append(('top_right', i, None))
        #     elif len(self.top_right[i])<9:
        #         card = self.top_right[i][-1]
        #         all_possible_target.append(('top_right', i, card))
        # 1.3 all possible moves
        for area_s, index_s, card_s in all_possible_source:
            if card_s.suit == '花':
                # game = copy.deepcopy(self)
                # game.move((area_s, index_s), ('flower_grid', None))
                # result.append(game)
                # continue
                return [(area_s, index_s, ('flower_grid', None))]
                # when flower is available, you must move it to the flower_grid
            if card_s.suit in {'條', '餠', '萬'}: # target to top_right
                if card_s.suit == '條' and self.stick_collect_progress==card_s.value-1:
                    if self.circle_collect_progress>=card_s.value and self.wan_collect_progress>=card_s.value:
                        return [(area_s, index_s, ('top_right', None))]
                    else: pass
                elif card_s.suit == '餠' and self.circle_collect_progress==card_s.value-1:
                    if self.stick_collect_progress>=card_s.value and self.wan_collect_progress>=card_s.value:
                        return [(area_s, index_s, ('top_right', None))]
                    else: pass
                elif card_s.suit == '萬' and self.wan_collect_progress==card_s.value-1:
                    if self.stick_collect_progress>=card_s.value and self.circle_collect_progress>=card_s.value:
                        return [(area_s, index_s, ('top_right', None))]
                    else: pass
                else: continue
                game = copy.deepcopy(self)
                game.move((area_s, index_s), ('top_right', None))
                result.append(game)
            for area_t, index_t, card_t in all_possible_target:
                if area_t=='top_left': 
                    if area_s=='top_left': continue
                    else: pass
                elif area_t=='main':
                    if area_s=='main' and index_s==index_t: continue
                    if card_t is None: pass
                    elif card_s in {'條', '餠', '萬'} and card_t.suit in {'條', '餠', '萬'}:
                        if card_s.suit == card_t.suit: continue
                        if card_s.value != card_t.value-1: continue
                    else: continue
                else: continue
                game = copy.deepcopy(self)
                game.move((area_s, index_s), (area_t, index_t))
                result.append(game)
        # 2. collect all of a suit
        for suit in ['中', '發', '空']:
            if len([None for area_s, index_s, card_s in all_possible_source if card_s is not None and card_s.suit==suit])==4: 
                game = copy.deepcopy(self)
                game.collect_all_of_suit(suit)
                result.append(game)
        return result

    def solve(self, history=[]):
        print('solving...\n', self)
        history.append(self)
        if self.success(): return history
        moves = self.all_possible_moves()
        if len(moves)!=0:
            for game in moves:
                if game in history[-2:None:-1]: continue
                res = game.solve(history)
                if res is not None:
                    return history
        history.pop()
        return None

if __name__ == '__main__':
    random.seed(0)
    game = Game()
    print(game)
    solution = game.solve()
    if solution is None:
        print('No solution')
    else:
        print('Solution:')
        for i, game in enumerate(solution):
            print(f'Step {i+1}:')
            print(game)